818G - Four Melodies - CodeForces Solution

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
using i64 = uint64_t;
//using i128 = __int128;
#define MAXN 100005
#define MAXM 11
#define OP 0
#define CLO 1
#define PLUS 0
#define MINUS 1
#define MUL 2
#define HORZ 0
#define VERT 1
#define ITER 1000
#define INF 1e9
#define EPS 1e-9
#define MOD 1000000007
#define SRC 0
#define PUSH 0
#define POP 1
#define PI acos(-1)
#define UNVISITED INF
#define FOR 0
#define BACK 1
#define OK 2
#define H 19
#define HSH 3
typedef long long ll;
typedef ll hash_t;
//typedef __int128_t lint;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ll> ilp;
typedef pair<ll,ii> pl;
typedef pair<ll, ll> pll;
typedef pair<ll,int> ppll;
typedef pair<ll,int> li;
typedef pair<ll,ll> iv;
typedef pair<double,int> ip;
typedef tuple<int,int,int> iii;
typedef tuple<ll, ll, ll> tll;
typedef tuple<ld, int, int> iit;
typedef tuple<int,int,ll> i3;
typedef vector<vector<int>> vv;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<vector<ll>> vll;
//typedef complex<ld> cd;
typedef tuple<ll,int,int> tpl;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
#define pf push_front
#define bk back()
#define frnt front()
#define ins insert
#define er erase
#define sc second
#define fr first
#define mp make_pair
#define mt make_tuple
#define repl(i,x,y) for (int i = (x); i <= (y); ++i)
#define rep(i,x,y) for (int i = (x); i < (y); ++i)
#define rev(i,x,y) for (int i = (x); i >= (y); --i)
#define repd(i,x,y,d) for (int i = (x); i < (y); i += (d))
#define LSOne(S) (S & (-S))
#define trav(i,v) for (auto &i : v)
#define foreach(it,v) for (auto it = begin(v); it != end(v); ++it)
#define bend(v) begin(v), end(v)
#define rbend(v) (v).rbegin(), (v).rend()
#define sortarr(v) sort(bend(v))
#define rsortarr(v) sort(rbend(v))
#define rdup(v) v.er(unique(bend(v)), end(v))
#define rstreak(v) v.resize(unique(bend(v)) - begin(v))
#define extend(A,B) A.insert(end(A), bend(B))
#define sz(A) (int)(A.size())
#define fill(V) iota(bend(V), (0))
#define vfill(V, st) iota(bend(V), st)
#define sum(V) accumulate(bend(V), 0LL)
#define vsum(V, st) accumulate(bend(V), (ll)(st))
template<class T> bool ckmin(T &a, T b) { return a > b ? a = b, 1 : 0; };
template<class T> bool ckmax(T &a, T b) { return a < b ? a = b, 1 : 0; };
template<class T> void amax(T &a, T b, T c) { a = max(b, c); };
template<class T> void amin(T &a, T b, T c) { a = min(b, c); };
template<class T> T getmax(vector<T> &v) { return *max_element(bend(v)); };
template<class T> T getmin(vector<T> &v) { return *min_element(bend(v)); };
template<class vi> void distinct(vi &a) { sortarr(a); rdup(a); };
template<class T> int compress(vector<T> &v, T &val) { return (int)(lower_bound(bend(v), val) - begin(v)); };
template<class T> auto vfind(vector<T> &v, T val) {
    return find(bend(v), val);
}
template<class T> auto verase(vector<T> &v, T val) {
    return v.er(vfind(v, val));
}
template<class T> void revarr(vector<T> &v) { reverse(bend(v)); };
template<class T> void print(vector<T> &v, char end) { trav(i,v) cout << i << end;
}
 
mt19937 gen((int)(chrono::steady_clock::now().time_since_epoch().count()));
ll rng(ll l,ll r) {return uniform_int_distribution<ll>(l,r)(gen);}
 
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
ll gcd(ll a, ll b) {
    if (!a) return b;
    return gcd(b % a, a);
}
 
vector<ii> mv = {{-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}};
template<class T = long long>
struct mcmf {
    struct edge {
        int u, v, rv;
        T C, flow, w;
        edge(T C, T flow, int u, int v, T w, int rv) : C(C), flow(flow), u(u), v(v), w(w), rv(rv) {}
    };
 
    vector<edge> e;
    vector<vector<int>> g;
    vector<T> level;
    vector<int> parent, p_edge;
    int s, t, n;
    mcmf(int num) { //num is the total number of vertices to initialise to
        n = num, s = n - 2, t = n - 1;
        g.resize(n);
        parent.resize(n), level.resize(n), p_edge.resize(n);
    }
    
    void reset() {
        g.clear(), e.clear();
        g.resize(n);
    }
    
    void update(int src, int dst) { //update the source and sink
        s = src , t = dst;
    }
    
    void addEdge(int src, int dst, T cap, T cost) {
        edge e1 = edge(cap, 0, src, dst, cost, (int)(g[dst].size()));
        edge e2 = edge(0, 0, dst, src, -cost, (int)(g[src].size()));
        g[src].push_back((int)(e.size()));
        e.push_back(e1);
        g[dst].push_back((int)(e.size()));
        e.push_back(e2);
    }
 
    bool bfs() {
        for (int i = 0; i < n; ++i) {
            level[i] = numeric_limits<T>::max();
            parent[i] = -1;
        }
        vector<bool> inq(n, false);
        level[s] = 0;
        deque<int> q;
        q.push_front(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop_front();
            inq[u] = false;
            for (int i = 0; i < g[u].size(); i++) {
                edge &e1 = e[g[u][i]];
                if (level[e1.v] > level[u] + e1.w && e1.C > e1.flow) {
                    level[e1.v] = level[u] + e1.w;
                    parent[e1.v] = u;
                    if (!inq[e1.v]) {
                        inq[e1.v] = true;
                        q.push_back(e1.v);
                    }
                    p_edge[e1.v] = i;
                }
            }
        }
        if (level[t] == numeric_limits<T>::max()) return false;
        return true;
    }
 
    pair<T,T> run() { //first entry is max flow, second entry is min cost
        T res = 0, cost = 0;
        while (bfs()) {
            T flow = numeric_limits<T>::max();
            for (int curr = t; curr != s; curr = parent[curr]) {
                int pu = parent[curr], pr = p_edge[curr];
                flow = min(flow, e[g[pu][pr]].C - e[g[pu][pr]].flow);
            }
           
            res += flow;
            for (int curr = t; curr != s; curr = parent[curr]) {
                int pu = parent[curr], pr = p_edge[curr], bc = e[g[pu][pr]].rv;
                e[g[pu][pr]].flow += flow;
                cost += e[g[pu][pr]].w * flow;
                e[g[curr][bc]].flow -= flow;
            }
        }
        return {res, cost};
    }
    bool got_flow(int u, int v) {
        for (int &idx : g[u]) {
            edge &edg = e[idx];
            if (edg.v == v) return e.flow > 0;
        }
        return false;
    }
};

int lm[7], lst[MAXN];
int main() {
    fast_io();
    memset(lst, -1, sizeof(lst));
    memset(lm, -1, sizeof(lm));
    //int t; cin >> t;
    //while (t--) solve();
    int n; cin >> n;
    int tvertices = 4 + 2 * n + 2;
    mcmf<int> mf(tvertices);
    int s = tvertices - 2, t = tvertices - 1;
    //add edges betwee sources and melody vertices
    rep(i,0,4) mf.addEdge(s, i, 1, 0);
    //whenever we deal with adding n^2 edges, try to add edges in a chain
    rep(i,0,n) {
        int a; cin >> a;
        //add edge from medlody vertices to starting vertices of the subsequence
        rep(j,0,4) mf.addEdge(j, 4 + 2 * i, 1, -1);
        //add capacity edges because of vertex splitting
        mf.addEdge(4 + 2 * i, 4 + 2 * i + 1, 1, 0);
        //add edges between the second vertex and the sink to end the subsequence
        mf.addEdge(4 + 2 * i + 1, t, 1, 0);
        // add edges between valid neighbours in a subsequence
        if (lm[a % 7] != -1)  {
            mf.addEdge(4 + 2 * lm[a % 7] + 1, 4 + 2 * i, 1, -1);
            mf.addEdge(4 + 2 * lm[a % 7], 4 + 2 * i, INF, 0);
        }
        if (a - 1 > 0 && lst[a - 1] != -1)  mf.addEdge(4 + 2 * lst[a - 1] + 1, 4 + 2 * i, 1, -1);
        if (lst[a + 1] != -1)  mf.addEdge(4 + 2 * lst[a + 1] + 1, 4 + 2 * i, 1, -1);
        if (lst[a] != -1) { //jump along vertices with the same value and the same modulo to speedup
            mf.addEdge(4 + 2 * lst[a], 4 + 2 * i, INF, 0);
        }
        lm[a % 7] = lst[a] = i;
    }
    cout << -mf.run().sc;
}